'''
	希尔排序（又名分组插入排序或缩小增量排序）
	时间复杂度：最好：O(n) 平均： 最差：O(n^2)
	空间复杂度：O(1)
	稳定性：不稳定
	基本思想： 
			1.先将整个待排序列分割成若干子序列（由相隔某个“增量”的元素组成，一般取n/2的增量）
			2.分别进行直接插入排序
			3.依次缩小增量再排序，待整个序列中的元素基本有序（增量足够小）
			4.再对全体元素进行一次直接插入排序
'''
from tool import arr
def ShellSort(arr):
	n = len(arr)
	gap = n // 2
	while gap > 0:
		i = 0
		while i < gap:
			j = i + gap
			while j < n:
				if arr[j] < arr[j-gap]:
					tmp = arr[j]
					k = j - gap
					while k >= 0 and arr[k] > tmp:
						arr[k+gap] = arr[k]
						k = k - gap
					arr[k+gap] = tmp
				j = j+ gap
			i = i + 1
		gap = gap // 2
	return arr

if __name__ == '__main__':
	arr = ShellSort(arr)
	print(arr)